Search

A constraint satisfaction problem (CSP), \(\textsf {Max-CSP}(\mathcal {F})\) , is specified by a finite set of constraints \(\mathcal {F}\subseteq \lbrace [q]^k \rightarrow \lbrace 0,1\rbrace \rbrace\) for positive integers q and k. An instance of the problem on n variables is given by m applications of constraints from \(\mathcal {F}\) to subsequences of the n variables, and the goal is to find an assignment to the variables that satisfies the maximum number of constraints. In the (γ ,β)-approximation version of the problem for parameters 0 ≤ β ≤ γ ≤ 1, the goal is to distinguish instances where at least γ fraction of the constraints can be satisfied from instances where at most β fraction of the constraints can be satisfied. In this work, we consider the approximability of this problem in the context of sketching algorithms and give a dichotomy result. Specifically, for every family \(\mathcal {F}\) and every β < γ, we show that either a linear sketching algorithm solves the problem in polylogarithmic space or the problem is not solvable by any sketching algorithm in \(o(\sqrt {n})\) space. In particular, we give non-trivial approximation algorithms using polylogarithmic space for infinitely many constraint satisfaction problems. We also extend previously known lower bounds for general streaming algorithms to a wide variety of problems, and in particular the case of q=k=2, where we get a dichotomy, and the case when the satisfying assignments of the constraints of \(\mathcal {F}\) support a distribution on \([q]^k\) with uniform marginals. Prior to this work, other than sporadic examples, the only systematic classes of CSPs that were analyzed considered the setting of Boolean variables q = 2, binary constraints k =2, and singleton families \(|\mathcal {F}|=1\) and only considered the setting where constraints are placed on literals rather than variables. Our positive results show wide applicability of bias-based algorithms used previously by [47] and [41], which we extend to include richer norm estimation algorithms, by giving a systematic way to discover biases. Our negative results combine the Fourier analytic methods of [56], which we extend to a wider class of CSPs, with a rich collection of reductions among communication complexity problems that lie at the heart of the negative results. In particular, previous works used Fourier analysis over the Boolean cube to initiate their results and the results seemed particularly tailored to functions on Boolean literals (i.e., with negations). Our techniques surprisingly allow us to get to general q-ary CSPs without negations by appealing to the same Fourier analytic starting point over Boolean hypercubes. [ABSTRACT FROM AUTHOR]

Boolean functions used in symmetric-key encryption should have high higher-order nonlinearity to resist several known cryptographic attacks, such as algebraic attacks and low-degree approximation attacks. The higher-order nonlinearity also plays an important role in coding theory and theoretical computer science, since it relates to the covering radius of Reed–Muller codes and the Gowers norm, respectively. It is well-known that bent functions have the highest nonlinearity in an even number of variables and thus they possess the best ability to withstand fast correlation attacks and best affine approximation attacks. However, there is currently limited knowledge regarding the higher-order nonlinearity of bent functions because computing the higher-order nonlinearity, or even providing tight lower bounds, is an extremely hard task. In 1974, Dillon proposed two well-known classes of bent functions based on partial spread (in brief, PS), called PS − and PS + , respectively. He also exhibited a subclass of bent functions in PS − , known as partial spread affine plane(PS a p for short). In this paper, we provide a lower bound on the third-order nonlinearity of the simplest PS a p bent functions in n variables, where n ≥ 6 is even, by calculating the nonlinearities of all second-order derivatives of this kind of bent functions. Compared to the two known lower bounds on the third-order nonlinearity given by Carlet and Tang et al. respectively, our lower bound is much better than these two ones. [ABSTRACT FROM AUTHOR]

A neuron with binary inputs and a binary output represents a Boolean function. Our goal is to extract this Boolean function into a tractable representation that will facilitate the explanation and formal verification of a neuron's behavior. Unfortunately, extracting a neuron's Boolean function is in general an NP-hard problem. However, it was recently shown that prime implicants of this Boolean function can be enumerated efficiently, with only polynomial time delay. Building on this result, we first propose a best-first search algorithm that is able to incrementally tighten the inner and outer bounds of a neuron's Boolean function. Second, we show that these bounds correspond to truncated prime-implicant covers of the Boolean function. Next, we show how these bounds can be propagated in an elementary class of neural networks. Finally, we provide case studies that highlight our ability to bound the behavior of neurons. [ABSTRACT FROM AUTHOR]

There is a rising demand for low-cost, high-information-capacity optical signal processing. The number of devices is limited of performing different Boolean functions using a single unit. In the current manuscript, six basic logic gates, including OR, XOR, NAND, AND, NOR, and XNOR, are implemented in a single unit utilizing all-optical silicon microring resonator. At first, three microring resonators are used to get the AND, XOR and NOR logic functions. Then, beam combiners are used to get the OR, NAND and XNOR functions from AND, XOR, and NOR functions. In MATLAB, the suggested design is numerically simulated to verify the functions at an operational speed of nearly 260 Gbps. The required pump power for switching is only 1.95 mW for microring resonator based switch which is very less comparatively. Also, some performance parameters like "extinction ratio", "contrast ratio", "amplitude modulation", "on–off ratio", and "quality factor" are evaluated. To design the circuit practically, optimized parameters of the circuits have been selected. The obtained values of "extinction ratio" and "contrast ratio" are 14.97 dB and 19.03 dB, respectively. The value of AM is 0.17 dB which is less than 1 dB. The on–off ratio of the MRR is 35.10 dB which is much higher than expected. [ABSTRACT FROM AUTHOR]

Consider Tn and Sn to represent the full transformation semigroup and the symmetric group on the set Xn = {1, 2,…,n}, respectively. A subset S of Tn is called an intersecting family if any two transformations α,β ∈ S coincide at some point i ∈ Xn. An intersecting family S is called maximum if no other intersecting family S′ exists with |S′| > |S|. Frankl and Deza [On the maximum number of permutations with given maximal or minimal distance, J. Combin. Theory Ser. A 22(3) (1977) 352–360] established that the cardinality of a maximum intersecting family of Sn equals (n − 1)!. Subsequent research demonstrated that a maximum intersecting family of Sn forms a coset of a stabilizer of one point, as shown by Cameron and Ku [Intersecting families of permutations, European J. Combin. 24(7) (2003) 881–890] and independently by Larose and Malvenuto [Stable sets of maximal size in Kneser-type graphs, European J. Combin. 25(5) (2004) 657–673]. Define K(n,r) = {α ∈ Tn : |im(α)|≤ r}, where im(α) denotes the image set of α. This paper presents a formula for the cardinality of a maximum intersecting family of K(n,r). It then characterizes the maximum intersecting families of K(n,r) and concludes by determining the number of maximum intersecting families of K(n,r). [ABSTRACT FROM AUTHOR]

A functionally complete Boolean operator is sufficient for computational circuits of arbitrary complexity. We connected YES (buffer) with NOT (inverter) and two NOT four-way junction (4J) DNA gates to obtain IMPLY and NAND Boolean functions, respectively, each of which represents a functionally complete gate. The results show a technological path towards creating a DNA computational circuit of arbitrary complexity based on singleton NOT or a combination of NOT and YES gates, which is not possible in electronic computers. We, therefore, concluded that DNA-based circuits and molecular computation may offer opportunities unforeseen in electronics. [ABSTRACT FROM AUTHOR]

Rotation symmetric Boolean functions are good candidates for stream ciphers because they have such advantages as simple structure, high operational speed and low implement cost. Recently, Mesnager et al. proposed for the first time an efficient method to construct balanced rotation symmetric Boolean functions with optimal algebraic immunity and good nonlinearity for an arbitrary even number of variables. However, the algebraic degree of their constructed n -variable (n > 4) function is always less than the maximum value n − 1. In this paper, by modifying the support of Boolean functions from Mesnager et al.'s construction, we present two new constructions of balanced even-variable rotation symmetric Boolean functions with optimal algebraic immunity as well as higher algebraic degree and nonlinearity. The algebraic degree of Boolean functions in the first construction reaches the maximum value n − 1 if n 2 is odd and n 2 ≠ (2 k + 1) 2 or (2 k + 1) 2 + 2 for integer k , while that of the second construction reaches the maximum value for all n. Moreover, the nonlinearities of Boolean functions in both two constructions are higher than that of Mesnager et al.'s construction. [ABSTRACT FROM AUTHOR]

This paper considers inequivalent monotone Boolean functions of an arbitrary number of variables, two monotone Boolean functions are equivalent if one can be obtained from the other by permuting the variables. It focuses on some inequivalent monotone Boolean functions with three and four types of equivalent variables, where the variables are either dominant or dominated. The paper provides closed formulas for their enumeration as a function of the number of variables. The problem we deal with is very versatile since inequivalent monotone Boolean functions are monotonic simple games, structures that are used in many fields such as game theory, neural networks, artificial intelligence, reliability or multiple-criteria decision-making. [ABSTRACT FROM AUTHOR]

An endomorphism of a finite algebra is said to be highest if its pre-period is greater than or equal to the pre-period of all its endomorphisms. In this paper, we characterize all highest endomorphisms of a Boolean lattice. [ABSTRACT FROM AUTHOR]

Memristors are considered promising energy-effcient artificial intelligence hardware, which can eliminate the von Neumann bottleneck by parallel in-memory computing. The common imperfection-enabled memristors are plagued with critical variability issues impeding their commercialization. Reported approaches to reduce the variability usually sacrifice other performances, e.g., small on/off ratios and high operation currents. Here, we demonstrate an unconventional Ag-doped nonimperfection diffusion channel-enabled memristor in van der Waals indium phosphorus sulfide, which can combine ultralow variabilities with desirable metrics. We achieve operation voltage, resistance, and on/off ratio variations down to 3.8, 2.3, and 6.9% at their extreme values of 0.2 V, 1011 ohms, and 108, respectively. Meanwhile, the operation current can be pushed from 1 A to 1 pA at the scalability limit of 6 nm after Ag doping. Fourteen Boolean logic functions and convolutional image processing are successfully implemented by the memristors, manifesting the potential for logic-in-memory devices and effcient non-von Neumann accelerators. [ABSTRACT FROM AUTHOR]

In modern block ciphers, the role of the substitution boxes is to generate ciphertext from the plaintext with high confusion. The immunity to various cryptographic attacks heavily depends on the strength of the S-box. In this article, a new method of obtaining highly nonlinear substitution boxes (S-boxes) is proposed. The subject method utilizes the artificial bee colony optimization technique. To check the immunity of the proposed S-boxes, the analysis of the proposed S-boxes is checked against the key performance indicators (KPIs) for S-boxes. The results obtained from KPIs are highly encouraging and the proposed S-boxes meet all the criteria needed for secure communication and storage of digital content. To rank the proposed S-box and the recently published S-boxes, the technique for order preference by similarity to an ideal solution is discussed for the first time for the S-boxes. [ABSTRACT FROM AUTHOR]

In this work, a complementary metal‐oxide‐semiconductor (CMOS) based leaky‐integrate and fire neuron has been proposed and investigated for neuromorphic applications. The neuron has been designed in Cadence Virtuoso and validated experimentally. It has been observed that the neuron consumes a maximum energy of 68.87 fJ/spike. The response of the neuron to excitatory as well as inhibitory inputs has been studied. To verify the applicability, the proposed neuron has been explored for reconfigurable threshold logic to implement various linearly separable Boolean functions including OR, AND, NOT, NOR, and NAND. Moreover, the threshold tunability of the neuron has also been verified and this property has been exploited to design threshold‐controlled logic gates. Instead of adjusting the weights of the applied inputs, the functionality of such gates can be controlled by changing the threshold of the neuron, simplifying the synaptic architecture of a neural network. Finally, a multilayer network has been designed and the recognition ability of the proposed network for MNIST handwritten digits has been verified with an accuracy of 96.93%. [ABSTRACT FROM AUTHOR]

A special class of monotone Boolean functions coming from shadow minimization theory of finite set-systems – KK-MBF functions – is considered. These functions are a descriptive model for systems of compatible groups of constraints, however, the class of all functions is unambiguously complex and it is sensible to study relatively simple subclasses of functions such as KK-MBF. Zeros of KK-MBF functions correspond to initial segments of lexicographic order on hypercube layers. This property is used to simplify the recognition. Lexicographic order applies priorities over constraints which is applicable property of practices. Query-based algorithms for KK-MBF functions are investigated in terms of their complexities. [ABSTRACT FROM AUTHOR]

Deutsch–Jozsa problem ( D J n ) showed for the first time that quantum computation can achieve exponential advantages over classical computers, which encouraged and laid the foundation for further research on quantum algorithms. A generalization of Deutsch–Jozsa problem ( D J n k , proposed by Phys Rev A 97:062331, 2018) maintains the exponential advantage when the parameter k is a constant. However, these achieved exponential advantages are just in the case that all outputs are required to be accurate. In contrast, this paper studies classical randomized decision tree complexities of D J n and D J n k . It is proved that the first complexity R 2 (D J n) ≤ 3 in all cases and the second complexity R 2 (D J n k) is constant when k n is constant for n being a large even number. As a result, for these cases, optimal bounded-error quantum algorithms of D J n and D J n k can only slightly accelerate the classical computation. [ABSTRACT FROM AUTHOR]

Most of the approaches published in the literature to construct S-boxes via Cellular Automata (CA) work by either iterating a finite CA for several time steps, or by a one-shot application of the global rule. The main characteristic that brings together these works is that they employ a single CA rule to define the vectorial Boolean function of the S-box. In this work, we explore a different direction for the design of S-boxes that leverages on Orthogonal CA (OCA), i.e. pairs of CA rules giving rise to orthogonal Latin squares. The motivation stands on the facts that an OCA pair already defines a bijective transformation, and moreover the orthogonality property of the resulting Latin squares ensures a minimum amount of diffusion. We exhaustively enumerate all S-boxes generated by OCA pairs of diameter 4 ≤ d ≤ 6 , and measure their nonlinearity. Interestingly, we observe that for d = 4 and d = 5 all S-boxes are linear, despite the underlying CA local rules being nonlinear. The smallest nonlinear S-boxes emerges for d = 6 , but their nonlinearity is still too low to be used in practice. Nonetheless, we unearth an interesting structure of linear OCA S-boxes, proving that their Linear Components Space is itself the image of a linear CA, or equivalently a polynomial code. We finally classify all linear OCA S-boxes in terms of their generator polynomials. [ABSTRACT FROM AUTHOR]

Dynamic linear functions on the boolean hypercube are functions which assign to each bit a positive weight, but the weights change over time. Throughout optimization, these functions maintain the same global optimum, and never have defecting local optima. Nevertheless, it was recently shown [Lengler, Schaller, FOCI 2019] that the (1 + 1) -Evolutionary Algorithm needs exponential time to find or approximate the optimum for some algorithm configurations. In this experimental paper, we study the effect of larger population sizes for dynamic binval, the extreme form of dynamic linear functions. We find that moderately increased population sizes extend the range of efficient algorithm configurations, and that crossover boosts this positive effect substantially. Remarkably, similar to the static setting of monotone functions in [Lengler, Zou, FOGA 2019], the hardest region of optimization for (μ + 1) -EA is not close the optimum, but far away from it. In contrast, for the (μ + 1) -GA, the region around the optimum is the hardest region in all studied cases.Kindly check and confirm the inserted city name is correctly identified.Correct. [ABSTRACT FROM AUTHOR]

Vectorial Boolean functions and codes are closely related and interconnected. On the one hand, various requirements of binary linear codes are needed for their theoretical interests but, more importantly, for their practical applications (such as few-weight codes or minimal codes for secret sharing, locally recoverable codes for storage, etc.). On the other hand, various criteria and tables have been introduced to analyse the security of S-boxes that are related to vectorial Boolean functions, such as the Differential Distribution Table (DDT), the Boomerang Connectivity Table (BCT), and the Differential-Linear Connectivity Table (DLCT). In previous years, two new tables have been proposed for which the literature was pretty abundant: the c-DDT to extend the DDT and the c-BCT to extend the BCT. In the same vein, we propose extended concepts to study further the security of vectorial Boolean functions, especially the c-Walsh transform, the c-autocorrelation, and the c-differential-linear uniformity and its accompanying table, the c-Differential-Linear Connectivity Table (c-DLCT). We study the properties of these novel functions at their optimal level concerning these concepts and describe the c-DLCT of the crucial inverse vectorial (Boolean) function case. Finally, we draw new ideas for future research toward linear code designs. [ABSTRACT FROM AUTHOR]

In this article, we provide some new limiting laws related to the free multiplicative law of large numbers and involving free and Boolean additive convolutions. Some examples of these limiting laws are presented within the framework of non-commutative probability theory. [ABSTRACT FROM AUTHOR]

Determining the weight distribution of all Reed-Muller codes is a huge and exciting problem that has been around since the sixties. Some progress has been made very recently, but we are still far from a solution. In this paper, we addressed the subproblem of determining as many codeword weights as possible in Reed-Muller codes of any lengths and any orders, which is decisive for determining their weight spectra (i.e., the lists of all possible weights in these codes). New approaches seem necessary for both the main problem and the subproblem. We first studied the difficulties and the limits of the approach, which consisted of using the usual primary and secondary constructions of Boolean functions for the purpose of determining as many weights as possible in Reed-Muller codes. We then introduced a way, different from the usual constructions, to generate Boolean functions in n variables having an algebraic degree bounded from above, without any restriction on n, and whose Hamming weights can be determined. This provided weights in Reed-Muller codes of any lengths 2n and any orders, allowing us to reach potentially new values in the weight spectra of Reed-Muller codes (as we illustrate with all Reed-Muller codes of lengths up to 221), with the related codewords being given with their supports and their algebraic normal forms being mathematically derived. [ABSTRACT FROM AUTHOR]

In design of secure cryptosystems and CDMA communications, the negabent functions play a significant role. The generalized Boolean functions have been extensively studied by Schmidt and established several important results in this setup. In this paper, several characteristics of the generalized nega-Hadamard transform (GNT) of generalized Boolean functions like inverse of GNT, generalized nega-cross correlation, generalized nega-Parseval's identity, relationship between GNT and generalized nega-cross correlation have analyzed. We studied the GNT for the derivative of this setup of functions and established the connection of generalized Walsh-Hadamard transform and GNT of derivatives of these functions. Also, the GNT of composition of vectorial Boolean function and generalized Boolean function is presented. Further, the generalized nega-convolution theorem for generalized Boolean function is obtained. [ABSTRACT FROM AUTHOR]

We present and analyze the relation between different types of linear codes through the (projective) dual transform. The considered codes are represented by a generator matrix or a characteristic vector, and the dual transform is defined in these terms. This allows us to extend its use to study codes with special properties, which we call self-polar, and their relation to Boolean functions. The self-polar codes are a special class of projective self-dual codes and are closely connected with self-dual and anti-self-dual bent functions. We also give some computational results for self-dual bent functions in eight variables. [ABSTRACT FROM AUTHOR]

We propose an effective version of the lift by derivation, an invariant that allows us to provide the classification of $ B(5,6,8) = RM(6, 8)/RM(4, 8) $. The main consequence is to establish that the covering radius of the Reed-Muller $ RM(4,8) $ is equal to 26. [ABSTRACT FROM AUTHOR]

Constructing Boolean functions with good cryptographic properties over a subset of vectors with fixed Hamming weight $ E_{n,k} \subset {{\rm{I\!F}}}_2^n $ is significant in lightweight stream ciphers like FLIP [14]. In this article, we have given a construction for a class of $ n $-variable weightwise almost perfectly balanced (WAPB) Boolean functions from known support of an $ n_0 $-variable WAPB Boolean function where $ n_0 < n $. This is a generalization of constructing a weightwise perfectly balanced (WPB) Boolean function by Mesnager and Su [16]. We have studied some cryptographic properties like ANF, nonlinearity, weightwise nonlinearities, and algebraic immunity of the functions. The ANF of this function is obtained recursively, which would be a low-cost implementation in a lightweight stream cipher. Further, we have presented another class of WAPB Boolean functions by modifying the earlier function, and we studied some of its cryptographic properties. The nonlinearity and weightwise nonlinearities of the modified functions improve substantially. [ABSTRACT FROM AUTHOR]

In computer science, a binary decision diagram is a data structure that is used to represent a Boolean function and to consider a compressed representation of relations. This paper considers the notation of T.B.T (total binary truth table), and introduces a novel concept of binary decision (hyper)tree and binary decision (hyper)diagram, directly and in as little time as possible, unlike previous methods. This study proves that every T.B.T corresponds to a binary decision (hyper)tree via minimum Boolean expression and presents some conditions on any given T.B.T for isomorphic binary decision (hyper)trees. Finally, for faster calculations and more complex functions, we offer an algorithm and so Python programming codes such that for any given T.B.T, it introduces a binary decision (hyper)tree. [ABSTRACT FROM AUTHOR]

In this paper, we study the value distributions of perfect nonlinear functions, i.e., we investigate the sizes of image and preimage sets. Using purely combinatorial tools, we develop a framework that deals with perfect nonlinear functions in the most general setting, generalizing several results that were achieved under specific constraints. For the particularly interesting elementary abelian case, we derive several new strong conditions and classification results on the value distributions. Moreover, we show that most of the classical constructions of perfect nonlinear functions have very specific value distributions, in the sense that they are almost balanced. Consequently, we completely determine the possible value distributions of vectorial Boolean bent functions with output dimension at most 4. Finally, using the discrete Fourier transform, we show that in some cases value distributions can be used to determine whether a given function is perfect nonlinear, or to decide whether given perfect nonlinear functions are equivalent. [ABSTRACT FROM AUTHOR]

In this article, we investigate meandric systems having one shallow side: the arch configuration on that side has depth at most two. This class of meandric systems was introduced and extensively examined by I. P. Goulden, A. Nica, and D. Puder [Int. Math. Res. Not. IMRN 2020 (2020), 983-1034]. Shallow arch configurations are in bijection with the set of interval partitions. We study meandric systems by using moment-cumulant transforms for noncrossing and interval partitions, corresponding to the notions of free and Boolean independence, respectively, in non-commutative probability. We obtain formulas for the generating series of different classes of meandric systems with one shallow side by explicitly enumerating the simpler, irreducible objects. In addition, we propose random matrix models for the corresponding meandric polynomials, which can be described in the language of quantum information theory, in particular that of quantum channels. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Donghua University (English Edition) is the property of Journal of Donghua University Editorial Board and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Aaronson defined Forrelation (2010) as a measure of correlation between a Boolean function f and the Walsh–Hadamard transform of another function g . In a recent work, we have studied different cryptographically important spectra of Boolean functions through the lens of Forrelation. In this paper, we explore a similar kind of correlation in terms of nega-Hadamard transform. We call it nega-Forrelation and obtain a more efficient sampling strategy for nega-Hadamard transform compared to the existing results. Moreover, we present an efficient sampling strategy for nega-crosscorrelation (and consequently nega-autocorrelation) spectra too, by tweaking the nega-Forrelation technique. Finally, we connect the hidden shift finding algorithm for bent functions (Rötteler, 2010) with the Forrelation algorithm and extend it for the negabent functions. [ABSTRACT FROM AUTHOR]

A Boolean function f on n variables is said to be a bent function if the absolute value of all its Walsh coefficients is 2 n / 2 . Our main result is a new asymptotic lower bound on the number of Boolean bent functions. It is based on a modification of the Maiorana–McFarland family of bent functions and recent progress in the estimation of the number of transversals in latin squares and hypercubes. By-products of our proofs are the asymptotics of the logarithm of the numbers of partitions of the Boolean hypercube into 2-dimensional affine and linear subspaces. [ABSTRACT FROM AUTHOR]

The Patterson–Wiedemann (PW) construction, which is defined for an odd number n of variables with n being the product of two distinct prime numbers p and q, can be interpreted as idempotent functions which are represented by the (d, r)-interleaved sequences formed by all-zero and all-one columns, where r = (2 p - 1) (2 q - 1) and d = (2 n - 1) r . We here study a modified form of the PW construction, which only requires 2 n - 1 (= d r) be a composite number, by relaxing the constraint on the values of d and r. We first elaborate on the case n = 15 and consider the functions corresponding to the (217, 151)-interleaved sequences. Taking into account those satisfying f (α) = f (α 2 k) for all α ∈ F 2 n in this scenario, where k is a fixed divisor of n, we obtain Boolean functions with nonlinearity 16268 exceeding the bent concatenation bound. Then we extend our study for the case n = 11 and obtain Boolean functions with nonlinearity 996 represented by the (89, 23)-interleaved sequences, which equals the best known nonlinearity result. In the process, we show that there is the possibility to exceed the best known nonlinearities using the functions corresponding to those interleaved sequences. [ABSTRACT FROM AUTHOR]

Recently, several interesting constructions of vectorial Boolean functions with the maximum number of bent components (MNBC functions, for short) were proposed. However, many of them have component functions from the completed Maiorana-McFarland class M # . Moreover, no examples of MNBC functions containing component functions provably outside M # are known. In this paper, we classify all MNBC functions in six variables. Based on the analysis of the obtained equivalence classes, we propose several infinite families of MNBC functions with component functions outside the M # class. In particular, two of our new constructions are solutions to the open problem [Bapić et al (eds) Proceedings of the twelfth international workshop on coding and cryptography, 2022, Item 1., p. 9]. [ABSTRACT FROM AUTHOR]

Legal text retrieval serves as a key component in a wide range of legal text processing tasks such as legal question answering, legal case entailment, and statute law retrieval. The performance of legal text retrieval depends, to a large extent, on the representation of text, both query and legal documents. Based on good representations, a legal text retrieval model can effectively match the query to its relevant documents. Because legal documents often contain long articles and only some parts are relevant to queries, it is quite a challenge for existing models to represent such documents. In this paper, we study the use of attentive neural network-based text representation for statute law document retrieval. We propose a general approach using deep neural networks with attention mechanisms. Based on it, we develop two hierarchical architectures with sparse attention to represent long sentences and articles, and we name them Attentive CNN and Paraformer. The methods are evaluated on datasets of different sizes and characteristics in English, Japanese, and Vietnamese. Experimental results show that: (i) Attentive neural methods substantially outperform non-neural methods in terms of retrieval performance across datasets and languages; (ii) Pretrained transformer-based models achieve better accuracy on small datasets at the cost of high computational complexity while lighter weight Attentive CNN achieves better accuracy on large datasets; and (iii) Our proposed Paraformer outperforms state-of-the-art methods on COLIEE dataset, achieving the highest recall and F2 scores in the top-N retrieval task. [ABSTRACT FROM AUTHOR]

The Möbius transform is a linear circuit used to compute the evaluations of a Boolean function over all points on its input domain. The operation is very useful in finding the solution of a system of polynomial equations over GF(2) for obvious reasons. However the operation, although linear, needs exponential number of logic operations (around n · 2n−1 bit xors) for an n-variable Boolean function. As such, the only known hardware circuit to efficiently compute the Möbius Transform requires silicon area that is exponential in n. For Boolean functions whose algebraic degree is bound by some parameter d, recursive definitions of the Möbius Transform exist that requires only O(nd+1) space in software. However converting the mathematical definition of this space-efficient algorithm into a hardware architecture is a non-trivial task, primarily because the recursion calls notionally lead to a depth-first search in a transition graph that requires context switches at each recursion call for which straightforward mapping to hardware is difficult. In this paper we look to overcome these very challenges in an engineering sense. We propose a space efficient sequential hardware circuit for the Möbius Transform that requires only polynomial circuit area (i.e. O(nd+1)) provided the algebraic degree of the Boolean function is limited to d. We show how this circuit can be used as a component to efficiently solve polynomial equations of degree at most d by using fast exhaustive search. We propose three different circuit architectures for this, each of which uses the Möbius Transform circuit as a core component. We show that asymptotically, all the solutions of a system of m polynomials in n unknowns and algebraic degree d over GF(2) can be found using a circuit of silicon area proportional to m · nd+1 and circuit depth proportional to 2 · log2(n − d). In the second part of the paper we introduce a fourth hardware solver that additionally aims to achieve energy efficiency. The main idea is to reduce the solution space to a small enough value by parallel application of Möbius Transform circuits over the first few equations of the system. This is done so that one can check individually whether the vectors of this reduced solution space satisfy each of the remaining equations of the system using lower power consumption. The new circuit has area also bound by m · nd+1 and has circuit depth proportional to d · log2 n. We also show that further optimizations with respect to energy consumption may be obtained by using depth-bound Möbius circuits that exponentially decrease run time at the cost of additional logic area and depth.

We prove that if a Boolean function essentially depends on at least two variables, then it cannot be implemented by a circuit that consists of unreliable gates with at most two inputs each and is self-correcting with respect to at least some faults of an arbitrary number of gates. In view of the previous results, it suffices to establish this fact for linear functions. [ABSTRACT FROM AUTHOR]

The 93 minions of Boolean functions stable under left composition with the clone of self-dual monotone functions are described. As an easy consequence, all (C 1 , C 2) -clonoids of Boolean functions are determined for an arbitrary clone C 1 and for any clone C 2 containing the clone of self-dual monotone functions. [ABSTRACT FROM AUTHOR]

Let (0 , a 1 , ... , a d − 1) n denote the function f n (x 0 , x 1 , ... , x n − 1) of degree d in n variables generated by the monomial x 0 x a 1 ⋯ x a d − 1 and having the property that f n is invariant under cyclic permutations of the variables. Such a function f n is called monomial rotation symmetric (MRS). Much of this paper extends the work on quadratic MRS functions in a 2020 paper of the authors to the case of binomial RS functions, that is sums of two quadratic MRS functions. There are also some results for the sum of any number of quadratic MRS functions. [ABSTRACT FROM AUTHOR]

Rotation symmetric Boolean functions were introduced by Pieprzyk and Qu in the late 1990's. They showed that these functions are useful, among other things, in the design of fast hashing algorithms with strong cryptographic properties. The concept of rotation symmetric Boolean functions has been generalized to a class of functions known as k -rotation Boolean functions, where k divides n and n is the number of variables of the Boolean function. Analogous to the case of regular rotation symmetric Boolean functions, a monomial k -rotation Boolean function is called long k -cycle if the number of terms coincides with n / k and short k -cycle if the number of terms is less than n / k. In this work we characterize short k -cycles by providing specific generators for them. We also provide a count for the number of short k -cycles in n variables for a fixed degree and for a specified length. [ABSTRACT FROM AUTHOR]

The efficient manipulation of magnetization using spin‐orbit torques (SOTs) generated by heavy metals and topological insulators has attracted significant attention. However, the symmetry of these conventional materials makes it challenging to achieve deterministic switching of perpendicular magnetization by currents, which prevents the practical application of SOT‐based spintronic devices such as magnetic memories and logics. Here, a composition gradient in a TaxTi1‐x alloy is introduced and the field‐free magnetization switching in TaxTi1‐x/CoFeB heterostructures with controllable SOT efficiencies is realized. Additionally, by engineering the gradient with a tilting angle relative to the current injection arm of the device, highly asymmetric switching loops are achieved, which are attributed to tilted spin polarization. Based on these two switching types, namely field‐free switching and field‐assisted asymmetric switching, five programmable Boolean logic functions are successfully demonstrated using a single device. This work paves the way for high‐density computing‐in‐memory applications with industry compatible artificially‐designed asymmetric SOT materials. [ABSTRACT FROM AUTHOR]

In this paper, we study the class of those Boolean functions that are coset leaders of first order Reed-Muller codes. We study their properties and try to better understand their structure (which seems complex), by studying operations on Boolean functions that can provide coset leaders (we show that these operations all provide coset leaders when the operands are coset leaders, and that some can even produce coset leaders without the operands being coset leaders). We characterize those coset leaders that belong to the well known classes of direct sums of monomial Boolean functions and Maiorana-McFarland functions. Since all the functions of Hamming weight at most 2 n - 2 are automatically coset leaders, we are interested in constructing infinite classes of coset leaders having possibly Hamming weight larger than 2 n - 2 . [ABSTRACT FROM AUTHOR]

Encoding a dictionary into another representation means that all the words can be stored in the dictionary in a more efficient way. In this way, we can complete common operations in dictionaries, such as (1) searching for a word in the dictionary, (2) adding some words to the dictionary, and (3) removing some words from the dictionary, in a shorter time. Binary decision diagrams (BDDs) are one of the most famous representations of such encoding and are widely popular due to their excellent properties. Recently, some people have proposed encoding dictionaries into BDDs and some variants of BDDs and showed that it is feasible. Hence, we further investigate the topic of encoding dictionaries into decision diagrams. Tagged sentential decision diagrams (TSDDs), as one of these variants based on structured decomposition, exploit both the standard and zero-suppressed trimming rules. In this paper, we first introduce how to use Boolean functions to represent dictionary files and then design an algorithm that encodes dictionaries into TSDDs with the help of tries and a decoding algorithm that restores TSDDs to dictionaries. We utilize the help of tries in the encoding algorithm, which greatly accelerates the encoding process. Considering that TSDDs integrate two trimming rules, we believe that using TSDDs to represent dictionaries would be more effective, and the experiments also show this. [ABSTRACT FROM AUTHOR]

The classical hypercontractive inequality for the noise operator on the discrete cube plays a crucial role in many of the fundamental results in the Analysis of Boolean functions, such as the Kahn-Kalai-Linial theorem, Friedgut's junta theorem and the invariance principle of Mossel, O'Donnell and Oleszkiewicz. In these results the cube is equipped with the uniform (1/2-biased) measure, but it is desirable, particularly for applications to the theory of sharp thresholds, to also obtain such results for general p-biased measures. However, simple examples show that when p is small there is no hypercontractive inequality that is strong enough for such applications. In this paper, we establish an effective hypercontractivity inequality for general p that applies to 'global functions', i.e. functions that are not significantly affected by a restriction of a small set of coordinates. This class of functions appears naturally, e.g. in Bourgain's sharp threshold theorem, which states that such functions exhibit a sharp threshold. We demonstrate the power of our tool by strengthening Bourgain's theorem, making progress on two conjectures of Kahn and Kalai (both these conjectures were open when we arXived this paper in 2019; one of them was solved in 2022; the other is still open), and proving a p-biased analogue of the seminal invariance principle of Mossel, O'Donnell, and Oleszkiewicz. In this 2023 version of our paper we will also survey many further applications of our results that have been obtained by various authors since we arXived the first version in 2019. [ABSTRACT FROM AUTHOR]

The paper introduces partial set-theoretic relations for metasets and investigates their properties. Metaset is a concept of imprecise set designed to represent vague notions in Artificial Intelligence, whose idea stems from Boolean-valued techniques in classical set theory. The basic set relations are extended to functions valued in a Boolean algebra or unit interval. Important classical set theory axioms: extensionality and comprehension are formulated for metasets. The latter enables formal definitions of collections with blurred boundaries by using set-theory formulae. This facilitates representing and reasoning about imprecise data. [ABSTRACT FROM AUTHOR]

It is known that the smaller the values of Gowers U 2 and U 3 norms of a Boolean function, the greater its strength against linear and quadratic approximations. This article gives recursive relation between the Gowers U 2 and U 3 norms of Boolean functions and their restriction to hyperplanes. These results will help analyze the second and third-order Gowers norms of Boolean functions in a higher number of variables. [ABSTRACT FROM AUTHOR]

The nonlinearity of vectorial functions and of their restrictions to manifolds are defined as the Hamming distance to the set of affine mappings and of their restrictions to the manifold, respectively. Relations between the parameters of the nonlinearity of a vectorial function and their analogues for its coordinate functions and its restrictions to manifolds are established. An analogue of the Parseval identity for such parameters of vectorial functions is proved, which implies the upper bound (qk − 1)qn−k − qn/2−k for the nonlinearity of a mapping over a q-element field of n variables with k coordinates. Attainability conditions for this estimate are found, and a class of Boolean vectorial functions with high value of nonlinearity is constructed. Estimates characterizing the distribution of the nonlinearity of a vectorial function and of its restrictions to manifolds are obtained. [ABSTRACT FROM AUTHOR]

We prove that any (almost any) n-place Boolean function can be implemented by a logic circuit in the "conjunction, disjunction, implication, negation" basis admitting a conditional complete diagnostic test of length at most n (at most n − 1, respectively) relative to constant faults of type 0 on outputs of gates. [ABSTRACT FROM AUTHOR]

The paper studies the relationships between local affinities of a Boolean function and some notions of its degeneracy (differential degeneracy, algebraic degeneracy, affine splittability). New relations connecting the parameters of local affinities and degeneracies are obtained. Relationships between some types of degeneracy of Boolean functions are found. [ABSTRACT FROM AUTHOR]